package hdgeom.procedures;

import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.Vector;
import processing.core.*;


public class ConvexHullPVector {
	public final static int CWRIGHT = 1;
	public final static int CCWLEFT = -1;
	public final static int PARALLEL = 0;
	public Vector<PVector> pts;
	public Vector<PVector>hull;
	
	public ConvexHullPVector(Vector<? extends PVector> p){
		
		hull=computeHull(p);
	}
	
	public Vector<PVector> getConvexHull(){
		return hull;
	}
	
	private Vector<PVector> computeHull(Vector<? extends PVector> p) {
		pts = new Vector<PVector>(p);
		// pts.addAll(p);
		if (pts.size() < 3)
			return pts;
		return grahamScan();

	}

	/*public Vector<PVector> computeHullPolygon(Vector<PVector> p) {
		pts = new Vector<PVector>();
		pts.addAll(p);
		if (pts.size() < 3)
			return pts;
		return computeHull(p);

	}*/

	private Vector<PVector> computeHullOfSorted2(Vector<PVector> pts) {
		Vector<PVector> hull = new Vector<PVector>();
		PVector p0 = pts.firstElement();
		hull.add(p0);

		PVector p1 = pts.get(1);
		hull.add(p1);

		PVector p2 = pts.get(2);
		hull.add(p2);

		for (int i = 3; i < pts.size(); i++) {
			p0 = p1;
			p1 = p2;
			p2 = pts.get(i);
			hull.add(p2);

			while (relativeCCW(p0, p2, p1) == CWRIGHT) {
				hull.remove(hull.size() - 2);
				p1 = p0;
				p0 = hull.get(hull.size() - 3);
			}
		}
		return hull;
	}
	public static int relativeCCW(PVector p0, PVector p1, PVector p2) {
		double ar = parallelArea(p0, p1, p2);
		if (Math.abs(ar) < 0.00000001)
			return PARALLEL;
		if (ar > 0)
			return CCWLEFT;
		return CWRIGHT;
	}
	public static float parallelArea(double x0, double y0, double x1,
			double y1, double x2, double y2) {
		double d1X = x0 - x1;
		double d1Y = y0 - y1;
		double d2X = x0 - x2;
		double d2Y = y0 - y2;
		return (float)(d1X * d2Y - d2X * d1Y);
	}
	public static float parallelArea(PVector p0,PVector p1,PVector p2) {
		return parallelArea(p0.x,p0.y,p1.x,p1.y,p2.x,p2.y);
	}
	private Vector<PVector> computeHullOfSorted(Vector<PVector> pts) {
	//	Vector<PVector> hull = new Vector<PVector>();
		Stack<PVector>hull=new Stack<PVector>();
		PVector p0 = pts.firstElement();
		hull.add(p0);
		PVector p1 = pts.get(1);
		hull.add(p1);
		int n=pts.size();
		int i=2;
		while(i<n){
			p0 = hull.peek();
			p1 = hull.get(hull.size()-2);
			PVector s = pts.get(i);
			//int dir=PVecMath2D.relativeCCW(p0,p1,s);
			if (relativeCCW(p0,p1,s) !=CWRIGHT) {
				hull.add(s);
				i++;
			}
			else{
				hull.pop();
			}
		}
		return hull;
	}


	private Vector<PVector> grahamScan() {
		PVector pl = lowestPoint();
		PVector sub = new PVector(pl.x, pl.y);
		makeRelTo(sub);
		Collections.sort(pts, new Point2DComparator());
		sub.set(sub.x * -1f, sub.y * -1f);
		makeRelTo(sub);
		return computeHullOfSorted(pts);
	}

	private void makeRelTo(PVector p0) {
		for (int i = 0; i < pts.size(); i++) {
			PVector p = pts.get(i);
			PVector newP=PVector.sub(p, p0);
			p.set(newP.x, newP.y);
			
		}
	}

	private PVector lowestPoint() {
		PVector minP = pts.firstElement();
		for (int i = 1; i < pts.size(); i++) {
			PVector p = pts.get(i);
			if (p.y < minP.y || (p.y == minP.y && p.x < minP.x))
				minP = p;
		}
		return minP;
	}

	class Point2DComparator implements Comparator<PVector> {
		public int compare(PVector p1, PVector p2) {
			// TODO Auto-generated method stub
			
			double cArea = p1.x * p2.y - p2.x * p1.y;
			if (p1.x==p2.x&&p1.y==p2.y){
				System.out.println("the same");
			}
			if (cArea < 0)
				return -1;
			if (cArea > 0)
				return 1;
			double d1 = Math.abs(p1.x) + Math.abs(p1.y);
			double d2 = Math.abs(p2.x) + Math.abs(p2.y);
			//System.out.println("sameAngle");
			
			if (d1< d2)
				return -1;
			else
				return 1;
		}
	}

} // end class GrahamScan

